/**
 * 给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
 * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从1开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
 **/

#include<vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n=numbers.size();
        // Notice:只判断是否相等会超出时间限制，要进行剪枝
        // 为了便于剪枝，两个指针一个从前面一个从后面，双向逼近，不是同向移动
        for(int i=0, j=n-1; i<j;){
            int sum = numbers[i] + numbers[j];
            if(sum == target){
                // 算出结果就返回，不再进行剩下的计算，节省时间
                return {i+1, j+1};
            }
            else if(sum < target){
                ++i;
            }
            else{
                --j;
            }
        }
        return {-1, -1};
    }
};